// Copyright 2012 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package heap implements functions for the creation and manipulation of an
// array based max heap.  For more documentation on this data structure please
// see Heapsort and Priority Queue in chapter 6 of CLRS 2nd edition.
package heap

// Parent returns the index of the parent node.
func Parent(i int) int {
	return i >> 1
}

// Left returns the index of the left child.
func Left(i int) int {
	return i << 1
}

// Right returns the index of the right child.
func Right(i int) int {
	return (i << 1) + 1
}

type Heap []int

// BuildMaxHeap is used to create a MaxHeap based on data from an existing array
// of integers.  The zero spot in the array is not used for data to make
// indexing simpler so it is instead used to hold the size of the heap which may
// not equal the size of the array it was based on.
func BuildMaxHeap(d []int) Heap {
	l := len(d)
	h := make(Heap, l+1)
	h[0] = l
	for i := 0; i < l; i++ {
		h[i+1] = d[i]
	}
	for i := h[0] >> 1; i > 0; i-- {
		h.MaxHeapify(i)
	}
	return h
}

// Swap is used to exchange two nodes in the heap.
func (h Heap) Swap(i, j int) {
	t := h[i]
	h[i] = h[j]
	h[j] = t
}

// MaxHeapify is a recursive function that is used to restore (or establish) the
// max heap property.
func (h Heap) MaxHeapify(i int) {
	max := i
	l := Left(i)
	r := Right(i)
	if l < h[0] && h[max] < h[l] {
		max = l
	}
	if r < h[0] && h[max] < h[r] {
		max = r
	}
	if max != i {
		h.Swap(max, i)
		h.MaxHeapify(max)
	}
}

// Sort changes the heap into a sorted array of integers in O(n log n) time.
// TODO(gavaletz) this has an extra element at zero and we could return a slice
// that excludes h[0] or we could allocate a len(h) - 1 array and copy the items
// into that leaving the heap in tact.
func (h Heap) Sort() {
	for i := h[0]; i > 1; i-- {
		h.Swap(1, i)
		h[0]--
		h.MaxHeapify(1)
	}
}

// ExtractMax removes and returns the maximum value from the heap.
func (h Heap) ExtractMax() int {
	if h[0] < 1 {
		return 0
	}
	max := h[1]
	h[1] = h[h[0]]
	h[0]--
	h.MaxHeapify(1)
	return max
}

// IncreaseKey increases the key value for the ith node and moves it to its
// proper position in the heap.
func (h Heap) IncreaseKey(i, k int) {
	h[i] = k
	for {
		p := Parent(i)
		if p < 1 || h[i] <= h[p] {
			break
		}
		h.Swap(p, i)
		i = p
	}
}

// Insert adds a new node to the heap and uses IncreaseKey to move it to its
// proper position in the heap.
func (h Heap) Insert(k int) Heap {
	h[0]++
	h = append(h, k)
	h.IncreaseKey(h[0], k)
	return h
}
